package com.power.structure.heap;

/**
 * @description:
 * @author: jiangnan
 * @time: 2021/6/15 10:20 上午
 */
public class SmallHeap {

    int[] data;
    int CAPACITY = 60;
    int size = 0;

    public SmallHeap() {
        data = new int[CAPACITY];
    }


    public void add(int element) {
        data[size++] = element;
    }

    public void enQueue(int element) {
        add(element);
        shiftUp(size - 1);
    }

    private void shiftUp(int index) {
        while (index > 0 && data[index] < data[parent(index)]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    private void swap(int a, int b) {
        int tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }

    private int parent(int index) {
        return (index - 1) / 2;
    }

    public void display() {
        for (int i = 0; i < size; i++) {
            System.out.print(" "+data[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SmallHeap smallHeap = new SmallHeap();
        for (int i = 5; i >0 ; i--) {
            smallHeap.enQueue(i);
        }
        smallHeap.display();
    }
}
